1. Field of the Invention
The present invention relates to a technique of pattern matching for detecting common data in two multi-dimensional signal data items. More particularly, this invention is concerned with a data processing circuit useful for detecting a portion of one data item with which a portion of another data item is most consistent and detecting a magnitude of displacement (magnitude of movement) of one data item relative to another data item.
An art provided by the present invention can be adapted to, for example, motion detection for moving pictures or pattern recognition. The present invention can apply to one-dimensional data, two-dimensional data, or three-dimensional data, or generally, to multi-dimensional data as long as integral transform is carried out properly according to the number of the dimensions of the input data. The higher the number is, the larger the effect that can be expected. The subsequent description will be made by taking two-dimensional image data items as examples in consideration of the current situation in the market.
2. Description of the Related Art
For compressing data representing a moving picture, "motion compensation" is generally carried out. As far as a moving picture is concerned, when a current picture is segmented into areas, images in almost all the areas are not very different from images in corresponding areas in a previous picture which have been moved in a parallel way. From this viewpoint, once the magnitude of the movement is detected, what is needed in addition is data concerning minute differences between images moved in parallel and original images. This enable considerable data compression. Even the MPEG systems that have become international standards adopt "motion compensation" as the basis of image data compression.
For controlling a movable robot or driving a motor car automatically, it is necessary to measure a vector representing the velocity of an object in a camera picture. Based on the velocity vector, movement or drive is controlled. Moreover, even an automatic tracking camera for tracking a moving object in line with the movement requires "motion" detection.
For measuring the "motion," two-dimensional correlation is employed. Specifically, an area in a previous picture is moved by a vector (.DELTA.X, .DELTA.Y) two-dimensionally, and correlated two-dimensionally with a corresponding area in a current picture. A magnitude of movement (.DELTA.X, .DELTA.Y) maximizing the correlation is detected. The magnitude is the magnitude of a motion vector or a vector representing a "motion."
Assuming that a signal representing a pixel (x, y) in an area in a current picture is regarded as a(x, y), a signal representing a pixel in an area in a previous picture which is moved by a magnitude of movement (.DELTA.X, .DELTA.Y) is regarded as b(x-.DELTA.X, y-.DELTA.Y), the two-dimensional correlation between the corresponding areas is provided as a sum of absolute values of differences between two signals of the signals representing all pixels within the areas (See the expression (1)) or a sum of products between two signals (See the expression (2)). EQU C(.DELTA.X, .DELTA.Y)=.SIGMA..sub.x .SIGMA..sub.y .vertline.a(x, y)-b(x-.DELTA.X, y-.DELTA.Y).vertline. (1) EQU C(.DELTA.X, .DELTA.Y)=.SIGMA..sub.x .SIGMA..sub.y a(x, y) b(x-.DELTA.X, y-.DELTA.Y) (2)
These two-dimensional correlations are generally obtained by carrying out arithmetic operations in the real space so as to calculate the expressions. For the expression (2), a Fourier transform can be employed.
The expression (1) is expected to be minimum, when areas in previous and current pictures become consistent with each other. The expression (2) is expected to be maximum, when intensities of the areas in the previous and current pictures have a proportional relationship.
Using evaluation function of two-dimensional correlation given by the expression (1), a motion vector minimizing the difference between signals representing pixels in areas in previous and current pictures is detected. The evaluation function is suitable for a system in which both a motion vector (magnitude of movement) and difference signal (data indicating a difference between signals) are supplied, such as, to an MPEG system.
However, assuming that the size of areas to be correlated is N*N (where * means multiplication), and the size of areas exhibiting a motion vector to be detected is L*L, an arithmetic operation for calculating absolute values, subtraction, and addition, must be performed N.sup.7 L.sup.2 times. This leads to a drawback in that the number of arithmetic operations becomes very large.
By contrast, in the arithmetic operations needed to calculate a two-dimensional correction given by the expression (2), when a Fourier transform is employed, the number of arithmetic operations to be carried out is in the order of (N+L).sup.2 log(N+L). This leads to an advantage that the number of arithmetic operations can be minimized.
However, the evaluation function provided as a sum of products between two signals has a problem in that signals are incorrectly matched with signals representing pixels in a bright area. As is apparent from the expression (2), when b(x-.DELTA.X, y-.DELTA.Y) is large, even if the correlation with a(x, y) is small C(.DELTA.X, .DELTA.Y) becomes a large value. Specifically, the distribution of signals b(x-.DELTA.X, y-.DELTA.Y) varies depending on .DELTA.X and .DELTA.Y. This means that some normalization is needed.